<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Introduction to Local Search
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial094.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial096.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc186">13.4</A>&nbsp;&nbsp;Introduction to Local Search</H2><UL>
<LI><A HREF="tutorial095.html#toc93">Changing Tentative Values</A>
<LI><A HREF="tutorial095.html#toc94">Hill Climbing</A>
</UL>

<A NAME="toc93"></A>
<H3 CLASS="subsection"><A NAME="htoc187">13.4.1</A>&nbsp;&nbsp;Changing Tentative Values</H3>
From a technical point of view, the main difference between tree search
and <EM>local</EM> (or move-based) search is that tree search adds
assignments while local search changes them. 
During tree search
constraints get tightened when going down the tree, and this is undone
in reverse order when backing up the tree to a parent node. This fits
well with the idea of constraint propagation.<BR>
<BR>
It is characteristic of local search that a move produces
a small change, but it is not clear what effect this will have on the
constraints. They may become more or less satisfied.
We therefore need implementations of the constraints that monitor changes
rather than propagate instantiations. <BR>
<BR>
Local search can be implemented quite naturally in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> using the
<TT>repair</TT> library.
In essence, the difference between implementing tree search techniques
and local 
search in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> is that, instead of instantiating variables during
search, local search progresses by changing <EM>tentative</EM> values of
variables.
For the satisfiability example of the last section, we can change
<CODE>min_conflicts</CODE> to
<CODE>local_search</CODE> by simply replacing the <CODE>guess</CODE> predicate by the
predicate <CODE>move</CODE>:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
local_search(Vars) :-
    conflict_constraints(cs,List), 
    ( List = [] -&gt; 
        set_to_tent(Vars)
    ; List = [Constraint|_] -&gt;
        term_variables(Constraint,[Var|_]),
        move(Var),
        local_search(Vars)
    ).

move(Var) :-
    Var tent_get Value,
    NewValue is (1-Value),
    Var tent_set NewValue.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
There is no guarantee that this move will reach a better assignment,
since <EM>NewValue</EM> may violate more constraints than the
original <EM>Value</EM>.<BR>
<BR>
<A NAME="toc94"></A>
<H3 CLASS="subsection"><A NAME="htoc188">13.4.2</A>&nbsp;&nbsp;Hill Climbing</H3>
To find a neighbour which overall increases the number of satisfied
constraints we could replace <CODE>local_search</CODE> with the predicate
<CODE>hill_climb</CODE>: 

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
hill_climb(Vars) :-
    conflict_constraints(cs,List), 
    length(List,Count),
    ( Count = 0 -&gt; 
          set_to_tent(Vars) 
    ; try_move(List,NewCount), NewCount &lt; Count -&gt;
          hill_climb(Vars)
    ;
          write('local optimum: '), writeln(Count)
    ).

try_move(List,NewCount) :-
      select_var(List,Var),
      move(Var),
      conflict_constraints(cs,NewList), 
      length(NewList,NewCount).

select_var(List,Var) :-
    member(Constraint,List),
    term_variables(Constraint,Vars),
    member(Var,Vars).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Some points are worth noticing:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Constraint satisfaction is recognised
by finding that the conflict constraint set is empty.
<LI CLASS="li-itemize">The move operation and the acceptance test
are within the condition part of the if-then-else construct.
As a consequence, if the acceptance test fails (the move does not
improve the objective) the move is automatically 
undone by backtracking.
</UL>
The code for <CODE>try_move</CODE> is very inefficient, because it
repeatedly goes through the whole list of conflict constraints to
count the number of constraints in conflict.
The facility to propagate tentative values supports more efficient
maintenance of the number constraints in conflict. 
This technique is known as maintenance of <EM>invariants</EM> (see
[<A HREF="tutorial133.html#Localizer"><CITE>18</CITE></A>]).
For the propositional satisfiability example we can maintain the
number of satisfied clauses to make the hill climbing implementation
more efficient. <BR>
<BR>
The following program not only monitors each clause for conflict, but
it also records in a boolean variable whether the clause is satisfied.
Each tentative assignment to the variables is propagated to the
tentative value of the boolean.
The sum of the boolean <CODE>BSum</CODE> records for any tentative
assignment of the propositional variables, the number of satisfied
clauses.
This speeds up hill climbing because, after each move, its effect on
the number of satisfied clauses is automatically computed by the
propagation of tentative values.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
prop_sat_2(Vars) :-
    Vars = [X1,X2,X3],
    tent_init(Vars),
    clause_cons(X1 or neg X2 or X3,B1),
    clause_cons(neg X1 or neg X2,B2),
    clause_cons(X2 or neg X3,B3),
    BSum tent_is B1+B2+B3,
    hill_climb_2(Vars,BSum).

clause_cons(Clause,B) :- 
    Clause $= 1 r_conflict cs,
    B tent_is Clause.

hill_climb_2(Vars,BSum) :-
    conflict_constraints(cs,List),
    BSum tent_get Satisfied,
    ( List=[] -&gt; 
          set_to_tent(Vars) 
    ; select_var(List,Var), move(Var), tent_get(BSum) &gt; Satisfied -&gt;
          hill_climb_2(Vars,BSum)
    ;
          write('local optimum: '), writeln(Count)
    ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
To check whether the move is uphill, we retrieve the tentative
value of <CODE>BSum</CODE> before and after the move is done. 
Remember that, since the move operator changes the tentative values of
some variable, the <CODE>tent_is</CODE> primitive will automatically
update the <CODE>BSum</CODE> variable.<BR>
<BR>
This code can be made more efficent by recording more
invariants, as described in [<A HREF="tutorial133.html#cp99wkshoptalk"><CITE>28</CITE></A>].<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	Local 
search can be implemented
in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> with the <TT>repair</TT> library.
Invariants can be implemented by tentative value propagation using
<TT>tent_is/2</TT>.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 13.4: Local Search and Invariants</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial094.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial091.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial096.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
